#!/usr/bin/python2
# -*- coding: UTF-8 -*-

def merge(a, b):
    r = []
    i = j = 0
    while j < len(a) and i < len(b):
        if a[j] < b[i]:
            r.append(a[j])
            j += 1
        else:
            r.append(b[i])
            i += 1

    if j == len(a):
        for k in b[i:]:
            r.append(k)
    else:
        for k in a[j:]:
            r.append(k)

    return r


def merge_sort(arr):
    if len(arr) < 2:
        return arr
    middle = len(arr)/2
    left = merge_sort(arr[:middle])
    rigit = merge_sort(arr[middle:])
    return merge(left, rigit)


if __name__ == '__main__':
    a = [50, 14, 2, 34, 43, 21, 19]
    print (merge_sort(a))

